package algorithm.leetcode.I1to100;

public class Q53 {

    public int maxSubArray(int[] nums) {
        if (nums.length == 1) return nums[0];

        int dp = nums[0];
        int maxSum = dp;

        for (int i = 1; i < nums.length; i++) {
            dp = Math.max(dp+nums[i], nums[i]);
            maxSum = Math.max(dp, maxSum);
        }
        return maxSum;
    }

    public static void main(String[] args) {
        int[] a = {-2,1,-3,4,-1,2,1,-5,4};
        Q53 q53 = new Q53();
        System.out.println(q53.maxSubArray(a));
    }

}
